package everyday;

import java.util.*;
import java.util.function.Consumer;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class T1048 {
    class Solution {
        public int longestStrChain(String[] words) {
            Map<String, Integer> cnt = new HashMap<String, Integer>();
            Arrays.sort(words, (a, b) -> a.length() - b.length());
            int res = 0;
            for (String word : words) {
                cnt.put(word, 1);
                for (int i = 0; i < word.length(); i++) {
                    String prev = word.substring(0, i) + word.substring(i + 1);
                    if (cnt.containsKey(prev)) {
                        cnt.put(word, Math.max(cnt.get(word), cnt.get(prev) + 1));
                    }
                }
                res = Math.max(res, cnt.get(word));
            }
            return res;
        }
    }

}
